package week_six;

import java.util.Arrays;

public class BestTimeToSellAndBuyStockWithFee_714 {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        // Move prices from [0..n-1] to [1..n]
        int[] pricesIn = new int[n + 1];
        pricesIn[0] = 0;
        for (int i = 1; i <= n; i++) pricesIn[i] = prices[i - 1];
        // Initialize DP array
        int[][] f = new int[n + 1][2];
        //从i到i+1的状态转移，必须把所有状态先初始化为负无穷
        //因为0会影响计算结果。
        for (int i = 0; i <= n; i++)
            Arrays.fill(f[i], (int) -1e9);

        f[0][0] = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= 1; j++) {
                if (j == 0)
                    f[i + 1][1] = Math.max(f[i + 1][1], f[i][j] - pricesIn[i + 1] - fee);
                if (j == 1)
                    f[i + 1][0] = Math.max(f[i + 1][0], f[i][j] + pricesIn[i + 1]);
                f[i + 1][j] = Math.max(f[i + 1][j], f[i][j]);
            }
        }

        return f[n][0];
    }
}
